// set standard header
#pragma once
#ifndef _SET_
#define _SET_
#ifndef RC_INVOKED
#include <xtree>

#if _HAS_CXX17
#include <xpolymorphic_allocator.h>
#endif // _HAS_CXX17

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new
_STD_BEGIN
// CLASS TEMPLATE _Tset_traits
template <class _Kty, // key/value type
    class _Pr, // comparator predicate type
    class _Alloc, // actual allocator type (should be value allocator)
    bool _Mfl> // true if multiple equivalent keys are permitted
class _Tset_traits { // traits required to make _Tree behave like a set
public:
    using key_type       = _Kty;
    using value_type     = _Kty;
    using key_compare    = _Pr;
    using allocator_type = _Alloc;
#if _HAS_CXX17
    using node_type = _Node_handle<_Tree_node<value_type, typename allocator_traits<_Alloc>::void_pointer>, _Alloc,
        _Node_handle_set_base, _Kty>;
#endif // _HAS_CXX17

    static constexpr bool _Multi = _Mfl;

    using value_compare = key_compare;

    static const _Kty& _Kfn(const value_type& _Val) { // extract key from element value
        return _Val;
    }
};

// CLASS TEMPLATE set
template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>>
class set : public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false>> { // ordered red-black tree of key values, unique keys
public:
    static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Kty, typename _Alloc::value_type>,
        _MISMATCHED_ALLOCATOR_MESSAGE("set<T, Compare, Allocator>", "T"));

    using _Mybase                = _Tree<_Tset_traits<_Kty, _Pr, _Alloc, false>>;
    using key_type               = _Kty;
    using key_compare            = _Pr;
    using value_compare          = typename _Mybase::value_compare;
    using value_type             = typename _Mybase::value_type;
    using allocator_type         = typename _Mybase::allocator_type;
    using size_type              = typename _Mybase::size_type;
    using difference_type        = typename _Mybase::difference_type;
    using pointer                = typename _Mybase::pointer;
    using const_pointer          = typename _Mybase::const_pointer;
    using reference              = value_type&;
    using const_reference        = const value_type&;
    using iterator               = typename _Mybase::iterator;
    using const_iterator         = typename _Mybase::const_iterator;
    using reverse_iterator       = typename _Mybase::reverse_iterator;
    using const_reverse_iterator = typename _Mybase::const_reverse_iterator;

    using _Alnode        = typename _Mybase::_Alnode;
    using _Alnode_traits = typename _Mybase::_Alnode_traits;

#if _HAS_CXX17
    using insert_return_type = _Insert_return_type<iterator, typename _Mybase::node_type>;
#endif // _HAS_CXX17

    set() : _Mybase(key_compare()) { // construct empty set from defaults
    }

    explicit set(const allocator_type& _Al)
        : _Mybase(key_compare(), _Al) { // construct empty set from defaults, allocator
    }

    set(const set& _Right)
        : _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(
                              _Right._Getal())) { // construct set by copying _Right
    }

    set(const set& _Right, const allocator_type& _Al)
        : _Mybase(_Right, _Al) { // construct set by copying _Right, allocator
    }

    explicit set(const key_compare& _Pred) : _Mybase(_Pred) { // construct empty set from comparator
    }

    set(const key_compare& _Pred, const allocator_type& _Al)
        : _Mybase(_Pred, _Al) { // construct empty set from comparator and allocator
    }

    template <class _Iter>
    set(_Iter _First, _Iter _Last) : _Mybase(key_compare()) { // construct set from [_First, _Last), defaults
        this->insert(_First, _Last);
    }

    template <class _Iter>
    set(_Iter _First, _Iter _Last,
        const key_compare& _Pred)
        : _Mybase(_Pred) { // construct set from [_First, _Last), comparator
        this->insert(_First, _Last);
    }

    template <class _Iter>
    set(_Iter _First, _Iter _Last, const allocator_type& _Al)
        : _Mybase(key_compare(), _Al) { // construct set from [_First, _Last), allocator
        this->insert(_First, _Last);
    }

    template <class _Iter>
    set(_Iter _First, _Iter _Last, const key_compare& _Pred, const allocator_type& _Al)
        : _Mybase(_Pred, _Al) { // construct set from [_First, _Last), defaults, and allocator
        this->insert(_First, _Last);
    }

    set& operator=(const set& _Right) { // assign by copying _Right
        _Mybase::operator=(_Right);
        return *this;
    }

    set(set&& _Right) : _Mybase(_STD move(_Right)) { // construct set by moving _Right
    }

    set(set&& _Right, const allocator_type& _Al)
        : _Mybase(_STD move(_Right), _Al) { // construct set by moving _Right, allocator
    }

    set& operator=(set&& _Right) _NOEXCEPT_COND(
        _Alnode_traits::is_always_equal::value&& is_nothrow_move_assignable_v<_Pr>) { // assign by moving _Right
        _Mybase::operator=(_STD move(_Right));
        return *this;
    }

    void swap(set& _Right) _NOEXCEPT_COND(noexcept(_Mybase::swap(_Right))) // strengthened
    { // exchange contents with non-movable _Right
        _Mybase::swap(_Right);
    }

    set(initializer_list<value_type> _Ilist) : _Mybase(key_compare()) { // construct from initializer_list, defaults
        this->insert(_Ilist);
    }

    set(initializer_list<value_type> _Ilist,
        const key_compare& _Pred)
        : _Mybase(_Pred) { // construct from initializer_list, comparator
        this->insert(_Ilist);
    }

    set(initializer_list<value_type> _Ilist, const allocator_type& _Al)
        : _Mybase(key_compare(), _Al) { // construct from initializer_list, allocator
        this->insert(_Ilist);
    }

    set(initializer_list<value_type> _Ilist, const key_compare& _Pred, const allocator_type& _Al)
        : _Mybase(_Pred, _Al) { // construct from initializer_list, comparator, and allocator
        this->insert(_Ilist);
    }

    set& operator=(initializer_list<value_type> _Ilist) { // assign initializer_list
        this->clear();
        this->insert(_Ilist);
        return *this;
    }

    using _Mybase::_Unchecked_begin;
    using _Mybase::_Unchecked_end;
};

#if _HAS_CXX17
template <class _Iter, class _Pr = less<_Iter_value_t<_Iter>>, class _Alloc = allocator<_Iter_value_t<_Iter>>,
    enable_if_t<conjunction_v<_Is_iterator<_Iter>, negation<_Is_allocator<_Pr>>, _Is_allocator<_Alloc>>, int> = 0>
set(_Iter, _Iter, _Pr = _Pr(), _Alloc = _Alloc())->set<_Iter_value_t<_Iter>, _Pr, _Alloc>;

template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>,
    enable_if_t<conjunction_v<negation<_Is_allocator<_Pr>>, _Is_allocator<_Alloc>>, int> = 0>
set(initializer_list<_Kty>, _Pr = _Pr(), _Alloc = _Alloc())->set<_Kty, _Pr, _Alloc>;

template <class _Iter, class _Alloc, enable_if_t<conjunction_v<_Is_iterator<_Iter>, _Is_allocator<_Alloc>>, int> = 0>
set(_Iter, _Iter, _Alloc)->set<_Iter_value_t<_Iter>, less<_Iter_value_t<_Iter>>, _Alloc>;

template <class _Kty, class _Alloc, enable_if_t<_Is_allocator<_Alloc>::value, int> = 0>
set(initializer_list<_Kty>, _Alloc)->set<_Kty, less<_Kty>, _Alloc>;
#endif // _HAS_CXX17

template <class _Kty, class _Pr, class _Alloc>
inline void swap(set<_Kty, _Pr, _Alloc>& _Left, set<_Kty, _Pr, _Alloc>& _Right)
    _NOEXCEPT_COND(noexcept(_Left.swap(_Right))) { // swap _Left and _Right sets
    _Left.swap(_Right);
}

// CLASS TEMPLATE multiset
template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>>
class multiset
    : public _Tree<_Tset_traits<_Kty, _Pr, _Alloc, true>> { // ordered red-black tree of key values, non-unique keys
public:
    static_assert(!_ENFORCE_MATCHING_ALLOCATORS || is_same_v<_Kty, typename _Alloc::value_type>,
        _MISMATCHED_ALLOCATOR_MESSAGE("multiset<T, Compare, Allocator>", "T"));

    using _Mybase                = _Tree<_Tset_traits<_Kty, _Pr, _Alloc, true>>;
    using key_type               = _Kty;
    using key_compare            = _Pr;
    using value_compare          = typename _Mybase::value_compare;
    using value_type             = typename _Mybase::value_type;
    using allocator_type         = typename _Mybase::allocator_type;
    using size_type              = typename _Mybase::size_type;
    using difference_type        = typename _Mybase::difference_type;
    using pointer                = typename _Mybase::pointer;
    using const_pointer          = typename _Mybase::const_pointer;
    using reference              = value_type&;
    using const_reference        = const value_type&;
    using iterator               = typename _Mybase::iterator;
    using const_iterator         = typename _Mybase::const_iterator;
    using reverse_iterator       = typename _Mybase::reverse_iterator;
    using const_reverse_iterator = typename _Mybase::const_reverse_iterator;

    using _Alnode        = typename _Mybase::_Alnode;
    using _Alnode_traits = typename _Mybase::_Alnode_traits;

    multiset() : _Mybase(key_compare()) { // construct empty set from defaults
    }

    explicit multiset(const allocator_type& _Al)
        : _Mybase(key_compare(), _Al) { // construct empty set from defaults, allocator
    }

    multiset(const multiset& _Right)
        : _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(
                              _Right._Getal())) { // construct set by copying _Right
    }

    multiset(const multiset& _Right, const allocator_type& _Al)
        : _Mybase(_Right, _Al) { // construct set by copying _Right, allocator
    }

    explicit multiset(const key_compare& _Pred) : _Mybase(_Pred) { // construct empty set from comparator
    }

    multiset(const key_compare& _Pred, const allocator_type& _Al)
        : _Mybase(_Pred, _Al) { // construct empty set from comparator and allocator
    }

    template <class _Iter>
    multiset(_Iter _First, _Iter _Last) : _Mybase(key_compare()) { // construct set from [_First, _Last), defaults
        this->insert(_First, _Last);
    }

    template <class _Iter>
    multiset(_Iter _First, _Iter _Last,
        const key_compare& _Pred)
        : _Mybase(_Pred) { // construct set from [_First, _Last), comparator
        this->insert(_First, _Last);
    }

    template <class _Iter>
    multiset(_Iter _First, _Iter _Last, const allocator_type& _Al)
        : _Mybase(key_compare(), _Al) { // construct set from [_First, _Last), allocator
        this->insert(_First, _Last);
    }

    template <class _Iter>
    multiset(_Iter _First, _Iter _Last, const key_compare& _Pred, const allocator_type& _Al)
        : _Mybase(_Pred, _Al) { // construct set from [_First, _Last), comparator, and allocator
        this->insert(_First, _Last);
    }

    multiset& operator=(const multiset& _Right) { // assign by copying _Right
        _Mybase::operator=(_Right);
        return *this;
    }

    multiset(multiset&& _Right) : _Mybase(_STD move(_Right)) { // construct set by moving _Right
    }

    multiset(multiset&& _Right, const allocator_type& _Al)
        : _Mybase(_STD move(_Right), _Al) { // construct set by moving _Right
    }

    multiset& operator=(multiset&& _Right) _NOEXCEPT_COND(
        _Alnode_traits::is_always_equal::value&& is_nothrow_move_assignable_v<_Pr>) { // assign by moving _Right
        _Mybase::operator=(_STD move(_Right));
        return *this;
    }

    template <class... _Valty>
    iterator emplace(_Valty&&... _Val) { // try to insert value_type(_Val...), favoring right side
        return _Mybase::emplace(_STD forward<_Valty>(_Val)...).first;
    }

    void swap(multiset& _Right) _NOEXCEPT_COND(noexcept(_Mybase::swap(_Right))) // strengthened
    { // exchange contents with non-movable _Right
        _Mybase::swap(_Right);
    }

    multiset(initializer_list<value_type> _Ilist)
        : _Mybase(key_compare()) { // construct from initializer_list, defaults
        this->insert(_Ilist);
    }

    multiset(initializer_list<value_type> _Ilist,
        const key_compare& _Pred)
        : _Mybase(_Pred) { // construct from initializer_list, comparator
        this->insert(_Ilist);
    }

    multiset(initializer_list<value_type> _Ilist, const allocator_type& _Al)
        : _Mybase(key_compare(), _Al) { // construct from initializer_list, allocator
        this->insert(_Ilist);
    }

    multiset(initializer_list<value_type> _Ilist, const key_compare& _Pred, const allocator_type& _Al)
        : _Mybase(_Pred, _Al) { // construct from initializer_list, comparator, and allocator
        this->insert(_Ilist);
    }

    multiset& operator=(initializer_list<value_type> _Ilist) { // assign initializer_list
        this->clear();
        this->insert(_Ilist);
        return *this;
    }

    using _Mybase::_Unchecked_begin;
    using _Mybase::_Unchecked_end;
};

#if _HAS_CXX17
template <class _Iter, class _Pr = less<_Iter_value_t<_Iter>>, class _Alloc = allocator<_Iter_value_t<_Iter>>,
    enable_if_t<conjunction_v<_Is_iterator<_Iter>, negation<_Is_allocator<_Pr>>, _Is_allocator<_Alloc>>, int> = 0>
multiset(_Iter, _Iter, _Pr = _Pr(), _Alloc = _Alloc())->multiset<_Iter_value_t<_Iter>, _Pr, _Alloc>;

template <class _Kty, class _Pr = less<_Kty>, class _Alloc = allocator<_Kty>,
    enable_if_t<conjunction_v<negation<_Is_allocator<_Pr>>, _Is_allocator<_Alloc>>, int> = 0>
multiset(initializer_list<_Kty>, _Pr = _Pr(), _Alloc = _Alloc())->multiset<_Kty, _Pr, _Alloc>;

template <class _Iter, class _Alloc, enable_if_t<conjunction_v<_Is_iterator<_Iter>, _Is_allocator<_Alloc>>, int> = 0>
multiset(_Iter, _Iter, _Alloc)->multiset<_Iter_value_t<_Iter>, less<_Iter_value_t<_Iter>>, _Alloc>;

template <class _Kty, class _Alloc, enable_if_t<_Is_allocator<_Alloc>::value, int> = 0>
multiset(initializer_list<_Kty>, _Alloc)->multiset<_Kty, less<_Kty>, _Alloc>;
#endif // _HAS_CXX17

template <class _Kty, class _Pr, class _Alloc>
inline void swap(multiset<_Kty, _Pr, _Alloc>& _Left, multiset<_Kty, _Pr, _Alloc>& _Right)
    _NOEXCEPT_COND(noexcept(_Left.swap(_Right))) { // swap _Left and _Right multisets
    _Left.swap(_Right);
}

#if _HAS_CXX17
namespace pmr {
    template <class _Kty, class _Pr = less<_Kty>>
    using set = _STD set<_Kty, _Pr, polymorphic_allocator<_Kty>>;

    template <class _Kty, class _Pr = less<_Kty>>
    using multiset = _STD multiset<_Kty, _Pr, polymorphic_allocator<_Kty>>;
} // namespace pmr
#endif // _HAS_CXX17
_STD_END
#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // RC_INVOKED
#endif // _SET_

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
